package Solution;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: tao
 * Date: 2023-11-14
 * Time: 14:29
 */
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
    /**
     * 110平衡二叉树
     *https://leetcode.cn/problems/balanced-binary-tree/description/
     */
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        return helper(root) != -1;
    }
    public int helper(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = helper(root.left);
        int right = helper(root.right);

        //不是平衡树的情况
        if(left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        //return Math.max(left, right) + 1;
        return left > right ? left + 1: right + 1;
    }

    /**
     * 104最大深度
     * https://leetcode.cn/problems/maximum-depth-of-binary-tree/
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return left > right ? left + 1 : right +1;
    }

    /**
     * 101对称二叉树
     * https://leetcode.cn/problems/symmetric-tree/description/
     * @param root
     * @return
     */
    //递归
    // public boolean isSymmetric(TreeNode root) {
    //     if(root == null) {
    //         return true;
    //     }
    //     return isSymmetricChild(root.left, root.right);
    // }
    // boolean isSymmetricChild(TreeNode rootLeft, TreeNode rootRight) {
    //     //没有左右节点
    //     if(rootLeft == null && rootRight == null) {
    //         return true;
    //     }
    //     //一个树为空，一个树不为空
    //     if(rootLeft == null || rootRight == null) {
    //         return false;
    //     }
    //     //左右子树都有，判断两子树是否相等
    //     if(rootLeft.val != rootRight.val) {
    //         return false;
    //     }
    //     //找左节点的左孩子和右节点的右孩子、左节点的右孩子和右节点的左孩子是否相等
    //     return isSymmetricChild(rootLeft.left, rootRight.right) && isSymmetricChild(rootLeft.right, rootRight.left);
    // }
    //非递归，用队列来存储二叉树的节点
    public boolean isSymmetric(TreeNode root) {
        //根节点或者根节点的左右子树为空，也是对称的
        if(root == null) {
            return true;
        }
        TreeNode rootLeft = root.left;
        TreeNode rootRight = root.right;
        if((rootLeft == null && rootRight == null)) {
            return true;
        }
        //左右节点都不为空的情况下
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(rootLeft);
        queue.offer(rootRight);
        while(!queue.isEmpty()) {
            rootLeft = queue.poll();
            rootRight = queue.poll();
            //判断两节点是否都为空
            if(rootLeft == null && rootRight == null) {
                continue;
            }
            //判断两节点是否只有一个空或者值不相等
            if((rootLeft == null || rootRight == null) || (rootLeft.val) != (rootRight.val)) {
                return false;
            }
            //判断两节点是否相等
            queue.offer(rootLeft.left);
            queue.offer(rootRight.right);

            queue.offer(rootLeft.right);
            queue.offer(rootRight.left);
        }
        return true;
    }
}
public class Test1 {

    public static void main(String[] args) {

    }
}
